#include "BTreeNode.h"

using namespace std;

BTLeafNode::BTLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read(pid, buffer);
}
 
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  int keyCount = 0;
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    // Does not actually "properly" count the keys. This checks every 12N+8 
    // buffer and see's if there's a non null value. Keep in mind, if the 
    // buffer doesn't have an initialized array, the if array returns true.
    if (buffer[i] != '\0')
      keyCount++;
    else
      return keyCount;
  }
  return keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  // Error out if the node is full
  if(getKeyCount() >= 85)
    return RC_NODE_FULL;

  // Find the first entry that is equal to or greater than the key
  int index;
  RC rc = locate(key, index);

  // Convert the pid, sid, and key into cstrings
  char cpid[5];
  sprintf(cpid, "%04d", rid.pid);
  char csid[5];
  sprintf(csid, "%04d", rid.sid);
  char ckey[5];
  sprintf(ckey, "%04d", key);
  
  // Insert the (key, rid) pair at the end
  if (rc == RC_NO_SUCH_RECORD)
  {
    strncpy(&buffer[index * 12    ], cpid, 4);
    strncpy(&buffer[index * 12 + 4], csid, 4);
    strncpy(&buffer[index * 12 + 8], ckey, 4);
    return 0;
  }

  //
  // Insert the key at the front
  //
  if (index == 0)
  {
    // Create a preBuffer for the first key
    char preBuffer[PageFile::PAGE_SIZE];
    memset(preBuffer, 0, PageFile::PAGE_SIZE);

    strncpy(preBuffer, cpid, 4);
    strncpy(&preBuffer[4], csid, 4);
    strncpy(&preBuffer[8], ckey, 4);

    // Copy the buffer into preBuffer at the end.
    strncpy(&preBuffer[12], buffer, PageFile::PAGE_SIZE - 12);

    // Copy the new filled up preBuffer back into buffer.
    strncpy(buffer, preBuffer, PageFile::PAGE_SIZE);

    return 0;
  }

  //
  // Insert the key somewhere in the middle.
  //
  // Split the node into two at the point where the new key should be inserted.
  char firstHalf[PageFile::PAGE_SIZE];
  memset(firstHalf, 0, PageFile::PAGE_SIZE);
  strncpy(firstHalf, buffer, index * 12);

  char secondHalf[PageFile::PAGE_SIZE];
  memset(secondHalf, 0, PageFile::PAGE_SIZE);
  strncpy(secondHalf, &buffer[index * 12], (PageFile::PAGE_SIZE - (index * 12)));
  
  // Place the (key, RecordId) pair at the end of the first half
  strncpy(&firstHalf[index * 12    ], cpid, 4);
  strncpy(&firstHalf[index * 12 + 4], csid, 4);
  strncpy(&firstHalf[index * 12 + 8], ckey, 4);
  // Copy the first half and the second half back into the buffer
  strcpy(buffer, firstHalf);
  strcpy(&buffer[index * 12 + 12], secondHalf);
  // Then return 0
  return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
  // This leaf node should be entirely full
  if (getKeyCount() != 85)
    return RC_INVALID_FILE_FORMAT;

  // Get the value of the middle key
  RC rc;
  int middleKey; 
  RecordId middleRid;
  if ((rc = readEntry(43, middleKey, middleRid)) < 0)
    return rc;

  // splitIndex delineates where the buffer should be split apart
  // The insertion needs to occur in the first half or the second half for the
  // nodes to have the mininum number of keys and pointers. If the key is less
  // than the middle key, then the split should occur at 42 so that the
  // insertion can occur in to the first half. The same logic for 43.
  int splitIndex;
  if (key < middleKey)
    splitIndex = 42;
  else
    splitIndex = 43;

  // Seperate the buffer into the first half or the second half delineated by
  // the split index.
  char firstHalf[PageFile::PAGE_SIZE];
  char secondHalf[PageFile::PAGE_SIZE];
  // Make the arrays blank
  memset(firstHalf, 0, PageFile::PAGE_SIZE);
  memset(secondHalf, 0, PageFile::PAGE_SIZE);

  strncpy(firstHalf, buffer, splitIndex * 12);
  strncpy(secondHalf, &buffer[splitIndex * 12], (85 - splitIndex) * 12);
  
  // Get the original page id
  char originalPageId[5];
  strncpy(originalPageId, &buffer[PageFile::PAGE_SIZE-4], 4);
  originalPageId[4] = '\0';

  // Set the original node with the first half
  memset(buffer, 0, PageFile::PAGE_SIZE);
  strcpy(buffer, firstHalf);
  // Set the sibling node with the second half
  memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
  strcpy(sibling.buffer, secondHalf);


  // Insert the (key, RecordId) pair into the correct node
  if (splitIndex == 42) // Insert the pair into the original
    rc = insert(key, rid);
  else // Insert the pair into the sibling
    rc = sibling.insert(key, rid);
  if (rc < 0)
    return rc;

  // Set the sibling key to the first key in the sibling node */
  RecordId notUsedRid;
  if ((rc = sibling.readEntry(0, siblingKey, notUsedRid)) < 0)
    return rc;

  // Set the sibling next node pointer to the original node pointer.
  if (originalPageId[0] != '\0')
    if ((rc = sibling.setNextNodePtr(atoi(originalPageId))) < 0)
      return rc;

  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    char charKey[5];
    strncpy(charKey, &buffer[i], 4);
    charKey[4] = '\0';

    // Every byte that is not data should be null.
    if (charKey[0] == '\0')
    {
      eid = (i - 8) / 12;
      return RC_NO_SUCH_RECORD;
    }

    int intKey = atoi(charKey);
    if (intKey >= searchKey)
    {
      eid = (i - 8) / 12;
      return 0;
    }
  }
  // If nothing is found, then return end of tree error.
  return RC_END_OF_TREE;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
  int index = eid * 12;

  char cpid[5];
  char csid[5];
  char ckey[5];

  strncpy(cpid, &buffer[index    ], 4);
  strncpy(csid, &buffer[index + 4], 4);
  strncpy(ckey, &buffer[index + 8], 4);

  cpid[4] = '\0';
  csid[4] = '\0';
  ckey[4] = '\0';

  // Return error when nothing is found
  if (cpid[0] == '\0' || csid[0] == '\0' || ckey[0] == '\0')
    return RC_NO_SUCH_RECORD;

  rid.pid = atoi(cpid);
  rid.sid = atoi(csid);
  key = atoi(ckey);

  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
  char nodePtr[5];
  strncpy(nodePtr, &buffer[PageFile::PAGE_SIZE-4], 4);
  nodePtr[4] = '\0';

  return atoi(nodePtr);
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  if(pid < 0)
    return RC_INVALID_PID;
  char chPid[5];
  sprintf(chPid, "%04d", pid);
  char *siblingPid = &buffer[PageFile::PAGE_SIZE-4];
  strncpy(siblingPid, chPid, 4);

  return 0;
}

//=============================================================================

BTNonLeafNode::BTNonLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
  int keyCount = 0;
  for (int i = 4; i < PageFile::PAGE_SIZE; i += 12)
  {
    if (buffer[i] != '\0')
      keyCount++;
    else
      return keyCount;
  }
  return keyCount;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  // Error out if the node is full
  if(getKeyCount() == 85)
    return RC_NODE_FULL;

  // Find the first entry that is equal to or greater than the key
  int index;
  RC rc = locate(key, index);

  // Convert the pid and key into cstrings
  char ckey[5];
  sprintf(ckey, "%04d", key);
  ckey[4] = '\0';
  char cpid[5];
  sprintf(cpid, "%04d", pid);
  cpid[4] = '\0';
  
  // Insert the key and pid pair at the end
  if (rc == RC_NO_SUCH_RECORD)
  {
    memcpy(&buffer[(index * 12) + 4], ckey, 4);
    memcpy(&buffer[(index * 12) + 8], cpid, 4);
    return 0;
  }

  //
  // Insert the key at the front
  //
  if (index == 0)
  {
    // Create a preBuffer for the first key
    char preBuffer[PageFile::PAGE_SIZE];
    memset(preBuffer, 0, PageFile::PAGE_SIZE);

    // Copy the first pid from buffer into the prebuffer
    // Copy the key and pid into prebuffer
    memcpy(preBuffer, buffer, 4);
    memcpy(&preBuffer[4], ckey, 4);
    memcpy(&preBuffer[8], cpid, 4);

    // Copy the buffer into preBuffer at the end.
    memcpy(&preBuffer[16], &buffer[4], PageFile::PAGE_SIZE - 16);
    // Copy the new filled up preBuffer back into buffer.
    memcpy(buffer, preBuffer, PageFile::PAGE_SIZE);

    return 0;
  }

  //
  // Insert the key somewhere in the middle.
  //
  // Split the node into two at the point where the new key should be inserted.
  char firstHalf[PageFile::PAGE_SIZE];
  memset(firstHalf, 0, PageFile::PAGE_SIZE);
  memcpy(firstHalf, buffer, index * 12);

  char secondHalf[PageFile::PAGE_SIZE];
  memset(secondHalf, 0, PageFile::PAGE_SIZE);
  memcpy(secondHalf, &buffer[index * 12], (PageFile::PAGE_SIZE - (index * 12)));
  
  // Place the (key, RecordId) pair at the end of the first half
  memcpy(&firstHalf[index * 12 + 4], ckey, 4);
  memcpy(&firstHalf[index * 12 + 8], cpid, 4);

  // Copy the first half and the second half back into the buffer
  memcpy(buffer, firstHalf, PageFile::PAGE_SIZE);
  memcpy(&buffer[index * 12 + 12], secondHalf, (PageFile::PAGE_SIZE - (index * 12 + 12)));

  return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
  // This leaf node should be entirely full
  if (getKeyCount() != 85)
    return RC_INVALID_FILE_FORMAT;

  // Get the value of the middle key
  char charMidKey[5];
  strncpy(charMidKey, &buffer[43*12+8], 4);
  charMidKey[4] = '\0';
  int middleKey = atoi(charMidKey);
  
  // splitIndex delineates where the buffer should be split apart
  // The insertion needs to occur in the first half or the second half for the
  // nodes to have the mininum number of keys and pointers. If the key is less
  // than the middle key, then the split should occur at 42 so that the
  // insertion can occur in to the first half. The same logic for 43.
  int splitIndex;
  if (key < middleKey)
    splitIndex = 42;
  else
    splitIndex = 43;

  // Seperate the buffer into the first half or the second half delineated by
  // the split index.
  char firstHalf[PageFile::PAGE_SIZE];
  memset(firstHalf, 0, PageFile::PAGE_SIZE);
  memcpy(firstHalf, buffer, splitIndex * 12);
  char secondHalf[PageFile::PAGE_SIZE];
  memset(secondHalf, 0, PageFile::PAGE_SIZE);
  memcpy(secondHalf, &buffer[splitIndex * 12], (85 - splitIndex) * 12);

  // Set the original node with the first half.
  memset(buffer, 0, PageFile::PAGE_SIZE);
  memcpy(buffer, firstHalf, PageFile::PAGE_SIZE);
  // Set the sibling node with the second half.
  memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
  memcpy(sibling.buffer, secondHalf, PageFile::PAGE_SIZE);

  RC rc;
  // Insert the (key, pid) pair into the correct node
  if (splitIndex == 42) // Insert the pair into the original
    rc = insert(key, pid);
  else // Insert the pair into the sibling
    rc = sibling.insert(key, pid);
  if (rc < 0)
    return rc;
  
  // Set the midkey to the first key in the sibling node */
  char chMidKey[5];
  strncpy(chMidKey, &buffer[8], 4);
  chMidKey[4] = '\0';
  midKey = atoi(charMidKey);

  return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    char charKey[5];
    strncpy(charKey, &buffer[i], 4);
    charKey[4] = '\0';
    int cmpKey = atoi(charKey);
    
    if (cmpKey > searchKey)
    {
      char charPid[5];
      strncpy(charPid, &buffer[i-8], 4);
      charPid[4] = '\0';
      
      pid = atoi(charPid);
      return 0;
    }
    if (cmpKey == searchKey)
    {
      char charPid[5];
      strncpy(charPid, &buffer[i-8], 4);
      charPid[4] = '\0';
      
      pid = atoi(charPid);
      return 0;
    }
  }
  
  // Just
  char charPid[5];
  strncpy(charPid, &buffer[PageFile::PAGE_SIZE-4], 4);
  charPid[4] = '\0';
  
  pid = atoi(charPid);
  return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  RC rc;

  if(pid1 < 0 || pid2 < 0)
    return RC_INVALID_PID;
  
  char chPid1[5];
  chPid1[4] = '\0';
  sprintf(chPid1, "%04d", pid1);
  strncpy(buffer, chPid1, 4);

  if ((rc = insert(key, pid2)) < 0)
    return rc;

  return 0;
}

// locate() is a helper function for the insert() function.
RC BTNonLeafNode::locate(int searchKey, int& eid)
{
  for (int i = 4; i < PageFile::PAGE_SIZE; i += 12)
  {
    char charKey[5];
    strncpy(charKey, &buffer[i], 4);
    charKey[4] = '\0';
    
    // Every byte that is not data should be null.
    if (charKey[0] == '\0')
    {
      eid = (i - 4) / 12;
      return RC_NO_SUCH_RECORD;
    }

    int cmpKey = atoi(charKey);
    if (cmpKey >= searchKey)
    {
      eid = (i - 4) / 12;
      return 0;
    }
  }
  // If nothing is found, then return end of tree error.
  return RC_END_OF_TREE;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::setNextNodePtr(PageId pid)
{
  if(pid < 0)
    return RC_INVALID_PID;
  char chPid[5];
  sprintf(chPid, "%04d", pid);
  char *siblingPid = &buffer[PageFile::PAGE_SIZE-4];
  strncpy(siblingPid, chPid, 4);

  return 0;
}
